package main

/**
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note:A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1
Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

解析:
	回溯+分治法
	借助栈进行回溯
*/

func pathSum(root *TreeNode, sum int) [][]int {
	res := [][]int{}
	findPath(root, sum, &res, []int{})
	return res
}

/**
res要一直是同一个，所以用的指针
stack并非每次都是同一个，每次append时，由于长度不够，会生成新的stack。
stack只要能把每次新加的值传递下去即可，不使用指针也可以完成这个任务

https://github.com/halfrost/LeetCode-Go/blob/0f4d331b99412538b8a934cbdfb4ca3064b4988a/Algorithms/0113.%20Path%20Sum%20II/113.%20Path%20Sum%20II.go#L13
*/
func findPath(root *TreeNode, sum int, res *[][]int, stack []int) {
	if root == nil {
		return
	}

	stack = append(stack, root.Val) //生成新的stack 与最初传入的stack分离，后续对findPath中操作不会影响上层
	//如果到达叶子节点，且叶子节点值等于sum剩余值，则表示找到满足的路线
	if sum == root.Val && root.Left == nil && root.Right == nil {
		*res = append(*res, append([]int{}, stack...))
		//stack = stack[:len(stack)-1]  //每次都会生成新的stack 所以不用考虑堆栈之间stack的相互影响 不用额外处理stack
		return
	}

	sum = sum - root.Val
	findPath(root.Left, sum, res, stack)
	findPath(root.Right, sum, res, stack)
}

func pathSum(root *TreeNode, sum int) [][]int {
	res := [][]int{}
	findSum(root, sum, &res, []int{})
	return res
}

func findSum(root *TreeNode, sum int, res *[][]int, stack []int) {
	if root == nil {
		return
	}

	stack = append(stack, root.Val)
	if sum == root.Val && root.Left == nil && root.Right == nil {
		*res = append(*res, stack)
		return
	}

	sum -= root.Val
	findSum(root.Left, sum, res, stack)
	findSum(root.Right, sum, res, stack)
}
